0470. 用 Rand7() 实现 Rand10()【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 拒绝采样
• 3. 🔗 引用

1. 📝 题目描述

• leetcode

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。

每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

---

示例 1：

输入: 1
输出: [2]

示例 2：

输入: 2
输出: [2,8]

示例 3：

输入: 3
输出: [3,8,10]

---

提示：

• 1 <= n <= 10^5

进阶：

• rand7()调用次数的 期望值 是多少?
• 你能否尽量少调用 rand7() ?

2. 🎯 s.1 - 拒绝采样

c

int rand10() {
    int num;
    do {
        num = (rand7() - 1) * 7 + rand7();
    } while (num > 40);
    return (num - 1) % 10 + 1;
}

js

/**
 * @return {number}
 */
var rand10 = function () {
  let num
  do {
    num = (rand7() - 1) * 7 + rand7() // 1~49 均匀
  } while (num > 40)
  return ((num - 1) % 10) + 1
}

py

class Solution:
    def rand10(self) -> int:
        while True:
            num = (rand7() - 1) * 7 + rand7()
            if num <= 40:
                return (num - 1) % 10 + 1

• 时间复杂度：期望 $O(1)$（每次采样成功概率 40/49）
• 空间复杂度：$O(1)$

算法思路：

• 调用两次 rand7() 生成 $[1,49]$ 的均匀分布
• 拒绝大于 40 的值，对 40 取模得到 $[1,10]$

3. 🔗 引用

• Expected value 期望值
  • wiki